COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	forwar[f83,jmc]		Doing everything by forward chaining
C00023 ENDMK
C⊗;
forwar[f83,jmc]		Doing everything by forward chaining

	Programs in Lisp and Prolog and fancier systems are
difficult to modify when the modification involves making
explicit information that it hidden in the goal structure.
Brian Smith's 3-Lisp proposes to mitigate this by making
the environment directly accessible.  Likewise my proposals
for making Prolog introspective, as partially implemented
by Peter Szeredi.  However, the real solution may be systems
that keep no hidden information.  They would represent all information
by sentences.

	Chuck Williams's ART does backward chaining by forward
chaining, because it reifies goals.  Consider a system that
does blind forward chaining; it does any deduction it sees
as possible.  At first sight this seems very bad, because
of the well known examples where it will generate incredible
quantities of junk, e.g. instances of commutativity if it is
reasoning with numbers.

	However, we don't have to give it the bare commutative
law.  We might reify the commutative law in some way so
that the conditions of applicability of the sentence that
contains the commutative law are very restrictive and require
as premisses not merely the facts but also a good reason
for using commutativity.  It isn't yet clear that this is
a good way to write reasoning systems, but there is
no obvious reason why it can't work.

Non-monotonicity enters in some way.  We can use it to resolve
ambiguity.  We also need to characterize the set of possible
deductions, etc.  Suppose we use  ab  and aspects.  How is this
more powerful than the shadowing done in Prolog programs?  It
seems to have more parameters.  (Should the Prolog cut have
parameters?)

Under what conditions can we have a program that maintains as
much normality as possible, i.e. as new facts are added, it
keeps circumscribing  ab.  It tries to maintain a database of
ground assertions, e.g. it maintains a truth value for
assertions like  flies(Tweety)  and  ab aspect1(Tweety,S0).
Even apart from non-monotonicity, it would be interesting to
ask what is required so that the database of ground assertions
will be finite and maintainable.  If the database is to be both
finite and deductively closed, we would have to avoid functions that
generate infinite sets.  The chief examples of these are  cons,
successor  and  result(e,s).  It is better to keep them and
restrict their use.  Perhaps we can formalize keeping only interesting
facts.

Attachment enters, especially to get meta-level statements.

1. What statements are required to make what amounts to a Prolog
interpreter in the forward going system.  Call the language Forward.

2. Concentrate on the blocks world.
Rewrite BLOCK3.LSP[f83,jmc] in the forward reasoning style.

3. Present systems do universals by shadowing statements behind each other.
If ∃x.¬p fails, then a statement whose premiss is ∀x.p can follow it.
Suppose we do it by actually making searches of the database or the
"current consciousness" and putting statements in the database or
current consciousness.  A slightly different idea is to allow universally
quantified statements to be premisses of rules.
Maybe nonexistence statements should be looked upon as somewhat different
from universal statements.  Non-existence statements about the database
should be distinguished from non-existence statements about the world
even though the former may be used explicitly as a way of non-monotonically
inferring the latter.

4. We may want statements of the form

	goal(find(x,p(x)), reason-why-we-want-it).

5. The map coloring problems may also provide suitable examples.

???
6. Should rules be allowed to have premisses not present explicitly
but which can be checked either by programs that examine the
database or examine the external world?  It may be especially
appropriate to use such premisses to inhibit certain deductions
by declaring some aspects abnormal.

7. One goal is to improve the position.

8. There is an alternative to a system that likes all possible
deductions equally and is made monogenic or nearly so by qualifications.
This is one which only accepts deduction of  should-do(x),  requiring
that the action be doable immediately.

9. Suppose we want to say that a certain action should be done unless
there is something better to do.  Here is how we do it with circumscription.

	¬ab aspect1(z,x) ⊃ do x
	¬ab aspect1(z,y) ⊃ do y
	better(u,v) ⊃ ab aspect1(u,v)
	better(x,y)

Circumscribing  ab  then leads to the conclusion  do x  and not to
the conclusion  do y.  Note the innovation in that the variable  z
in the first two equations is present only in the  ab  wff.

	Here's another way of doing it - perhaps simpler.

	∀z.¬better(z,x) ⊃ do x
	∀z.¬better(z,y) ⊃ do y
	better(x,y)
	¬ab aspect1(u,v) ⊃ ¬better(u,v)

10. All this means that we badly need a good way of doing circumscription.

11. Consider a formalization of knowledge, including knowledge of
universals and existentials, that is correct provided the domain is
finite and the knower can enumerate the possibilities.  If we use
these rules in general, we get a very strong system - possibly S5 like.

12. Another try at doing is-a hierarchies by circ.
The key is probably to do enough reification.

1983 Nov 26
see belief[f83,jmc]

Here is a beginning on a formalism of chains of wanting.

want(prop, reason) is the predicate

∀x l r.want(move(x,l),r) ⊃ want(clear x,Want(move(x,l),r))

or perhaps

∀x l r.true want(move(x,l),r) ⊃ true want(clear x,want(move(x,l),r))

if it seems important to keep only one kind of  want.

or if we parametrize with time

∀x l r t. true(want(move(x,l),r),t) ⊃ true(want(clear x,want(move(x,l),r))),t+1)

Another variant:

∀x l r.want(move(x,l),r) ⊃ want(clear x and clear l,want(move(x,l),r))

This leaves two problems.  First  want(move(x,l),r)  actually
gives rise to three desires.  We want  x  to be clear, we want  l
to be clear, and we want to do the move.  Second what do we do
after  x  and  l  are clear?

∀x l r.want(move(x,l),r) ∧ clear x ∧ clear l ⊃ should(immove(x,l))

Does  should  require a second reason argument?

∀x l r.want(clear x and clear l,r) ⊃ want(clear x,want(clear l,r))
This seems too rigid.  Maybe we can pursue two goals at once.

∀p q r.want(p,want(q,r)) ∧ true p ⊃ want(q,r)

∀x l r s.holds(want(move(x,l),want(q,r)),s) ∧ clear(x,s) ∧ clear(l,s)
	⊃ (λs'.holds(at(x,l),s') ∧ holds(want(q,l),s'))(result(immove(x,l),s))

1983 Nov 27

	Perhaps we should use the  result  formalism with the usual
axioms supplemented by axioms about goals.  The forward reasoner
will not deduce just anything.  The reasoning is controlled by the
want  predicates.

	It might be best to consider the problem of finding a way of
building a certain structure as a purely mathematical problem.  The idea
is to separate think events from events in the real world.  Our goal
is to find a sequence of actions that will build the structure.  We
don't imagine thinking during the building.  The means that the
argument of  want  is not an assertion to become true but the sequence
of actions.  Better use a different word then, say  find.
We then have the general form of the goal

	find(x, p(x)),

and if we are using EKL,  find  will then be a BINDOP.
Maybe it's  tofind(x,p(x)).

So our goal in the block stacker is

	tofind(steps, exists(t1,result(steps,s0))).

But then what's the answer?

Clearly once we have shown

	exists(t1,result(movelist ((A Table) (B C) (A B)),s0)),

we should be done.

Also  tofind(steps,better(result(steps,s0),s0))

It looks like  better  can be axiomatized in the blocks world
rather easily.

want(tower,s) ∧ isbase(u,tower) ∧ on2(u,table,s) ∧ on(x,u,tower) ∧ ¬on1(x,u,s)
∧ clear(u,s) ∧ clear(x,s) ⊃ better(result(move(x,u),s),s)

better(result(a,s),s) ⊃ good(a,s)

want(tower,s) ∧ isbase(u,tower) ∧ on2(u,table,s) ∧ on(x,u,tower) ∧ ¬on1(x,u,s)
∧ above(y,u,s) ∧ clear(y,s) ⊃ better(result(move(x,table),s),s)

want(tower,s) ∧ isbase(u,tower) ∧ on2(u,table,s) ∧ on(x,u,tower) ∧ ¬on1(x,u,s)
∧ above(y,x,s) ∧ clear(y,s) ⊃ better(result(move(x,table),s),s)

better(result(a,s),result(b,s)) ⊃ better1(a,b,s)

	The formalization of  better  in particular cases should be
the basis of a lot of AI planning research.

***
Nov 29

1. Can we formalize a plausible move generator to be used with the
better heuristic?

Dec 3

1. Here seems to be an example of the problem in its sharpest form.

	Suppose we have a collection of sentences of the form
{a[i] > a[j]} interpreted as saying that  a[i]  is better than  a[j].
We suppose that the relation  >  is transitive.  We also have a process
for generating a better object from a given one.  We want to apply it
to the best of the  a[i] in order to get something better yet.  Therefore,
we want to deduce in some way that  a[i0]  is the best.  Of course,
we readily deduce that it is better than any other specific  a[i].
To say that it is the best we must do a circumscription of some kind
to say that these are all there are.

2. The sticky present.

	We reason about the present situation, but this changes the
situation.  From one point of view, each reasoning step is about a
different situation.  This would be very difficult to handle, and we
don't do it that way - nor should computers.
Here is one way it can be done.  At the outer level, we may have a
physical situation.  The physical situation may be changing continuously,
but we can often regard it as persistent by thinking about processes.
Thus while each character I type changes the situation, I can think
about the fact that I am typing this note, and that is somewhat
persistent.  However, we often have to think about our thought
processes.  This can be handled (though perhaps its not necessary)
by separate meta-processes and even meta-meta-processes.  A meta
process works with a static database of facts about the process.
Deductions occurring in the meta-process don't change this database.

	Meta-processes do their work, resulting perhaps in an action
at a lower level; then they are usually flushed.  Meta-activity is
begun from scratch when it is triggered by suitable events at the
lower level.

Dec 5

want(p,s) ∧ holds(p,result(a,s)) ⊃ should(a,s)

holds(on(x,y),result(move(x,y),s))

want(on(x,y),s)

leads to  should(move(x,y),s).

This can be expressed in Prolog as

should(a,s) ← want(p,s),holds(p,result(a,s)).

Namely, we are looking to determine what we should do.

If we imagine that deducing should(a,s) results in the action  a
if  s  is the contemporary situation we're nearly there.
Namely, we rewrite (1) as

should(a,s) ← want(p,s),holds(p,result(a,s)),do(a).

We imagine that reaching the goal  do(a) causes  a  to be done.  It
also causes the goal  should(a',result(a,s))  to be established.

The above isn't quite Prolog, because it is assumed that  result(a,s)
is computed.  We may want a system that does this, but we can Prologize
it as follows:

should(a,s) ← want(p,s),results(s,a,s'),holds(p,s'),do(a).

This has the disadvantage that it explores all actions.  We can try

should(a,s) ← want(p,s),achieves(s,p,a,s'),do(a).

Perhaps the Prolog spirit is to make a loop out of it as

should(a,s) ← want(p,s),achieves(s,p,a,s'),should(a',s').

The detailed program will have lots of  asserts in it.

We do not express our grand goals with  want,  because  want
demands and action that achieves it.  Instead we have facts like
goal(exists(t1))  where this asks for a certain tower described
by such facts as  on(A,B,t1).   We have facts like

want(p,s) ← goal(q),helps(p,q,s).

and also we want to put  better  in it.  Maybe it's

should(a,s) ← feature(s,ss),better(ss',ss),achieves(s,ss,a,s'),should(a,s'),

but that's not quite right.

achieves(on(x,y),move(x,y),s,s') ← clear(x,s),clear(y,s),results(s,move(x,y),s')

The intent here is that  clear(x,s)  and  clear(y,s)  are not used
as goals to be achieved by action.  They may be taken as goals to
be verified.  They can become goals to be achieved by action only
through other processes - namely through the creation of a plan.

Would it hurt to have  move(x,y)  both as an action and as a goal?
Of course, we can have  performable(move(x,y))  or even  performed(move(x,y))
as a goal.

1983 Dec 5

How about

should(a,t) ← want(p,t),achieves(a,p,t),should(a,t+1)

where we are using times rather than situations?

The other idea is that wffs are parametrized by times but non-monotonically
are inferred to hold at future times unless this is contradicted.
In these circumstances it is better to use functions than predicates.